package com.school.chapter02.stack_;

/**/
@SuppressWarnings({"all"})
class Maze {
    //长宽为十
    final int LENGTH = 10;
    private Cell CELLS[][] ;

    private class Cellimpl implements Cell {

        private int x;
        private int y;
        private boolean visited = false;       //是否已经路过
        private char mark;                     //用于识别是否为墙，并在找通路后进行标记

        public int getX() {
            return x;
        }

        public void setX(int x) {
            this.x = x;
        }

        public int getY() {
            return y;
        }

        public void setY(int y) {
            this.y = y;
        }

        public boolean isVisited() {
            return visited;
        }

        public void setVisited(boolean visited) {
            this.visited = visited;
        }

        public char getMark() {
            return mark;
        }

        public void setMark(char mark) {
            this.mark = mark;
        }
    }

    /**
     * @param maze
     * @throws
     * @explain createMaze:
     */
    public void create(char maze[][]) {
        //输入二维迷宫地图（以二维字符数组形式），将其转为CELLS(二维cell)，及初始化地图过程
        CELLS = new Cell[LENGTH][LENGTH];//声明，而非实例化
        /**/
        for (int i = 0; i < maze.length; i++) {
            for (int j = 0; j < maze.length; j++) {
                /**/
                Cell cell = new Cellimpl();//CELLS的运行类型
                /**/
                char c = maze[i][j];

                /**/
                if (c == '1') {
                    cell.setMark('1');                         //1
                } else if (c == '0') {
                    cell.setMark('0');                         //0
                }
                cell.setX(i);                                  //
                cell.setY(j);                                  //
                cell.setVisited(false);                         //
                /**/
                CELLS[i][j] = cell;
            }
        }
    }

    /**
     * @throws
     * @explain print:
     */
    public void print() {//打印方法
        for (int i = 0; i < LENGTH; i++) {
            for (int j = 0; j < LENGTH; j++) {
                System.out.print(CELLS[i][j].getMark() + " ");
            }
            System.out.println();
        }
    }

    public Cell[][] getCELLS() {
        return CELLS;
    }

    /**
     * @param maze 地图
     * @param sx 开始x轴坐标
     * @param sy 开始y轴坐标
     * @param ex 结束x轴坐标
     * @param ey 结束y轴坐标
     * @return boolean truefalse
     * @throws
     * @explain findPath:
     */
    private static boolean findPath(Maze maze, int sx, int sy, int ex, int ey) {
        boolean flag = false;//返回是否能找到出路
        Cell[][] cells = maze.getCELLS();
        Stack stack = new Stack();
        //stack.init();
        /**/
        Cell startCell = cells[sx][sy];
        Cell endCell = cells[ex][ey];
        /**/
        stack.push(startCell);
        startCell.setVisited(true);                     //
        /**/
        while (!stack.isEmpty()) {
/** */
            Cell curCell = (Cell) stack.peek();
            if (curCell == endCell) {
                while (!stack.isEmpty()) {
                    Cell cell = (Cell) stack.pop();
                    cell.setMark('*');
                }
                flag = true;
            } else {
                /**/
                int x = curCell.getX();
                int y = curCell.getY();
                //探路的优先级是右、下、左、上，并把检查isVisited是否为false，可走就压栈，并把isVisited改为true
                if (cells[x + 1][y].getMark() == '0' && cells[x + 1][y].isVisited() == false) {
                    stack.push(cells[x + 1][y]);
                    cells[x + 1][y].setVisited(true);
                } else if (cells[x][y + 1].getMark() == '0' && cells[x][y + 1].isVisited() == false) {     //
                    stack.push(cells[x][y + 1]);
                    cells[x][y + 1].setVisited(true);
                } else if (cells[x - 1][y].getMark() == '0' && cells[x - 1][y].isVisited() == false) {     //
                    stack.push(cells[x - 1][y]);
                    cells[x - 1][y].setVisited(true);
                } else if (cells[x][y - 1].getMark() == '0' && cells[x][y - 1].isVisited() == false) {
                    stack.push(cells[x][y - 1]);                                                      //
                    cells[x][y - 1].setVisited(true);
                } else {
                    stack.pop();                                                                   //
                }
            }
        }
        return flag;
    }

    public static void main(String[] args) {
        /**/
        char[][] mazearr = {
                {'1', '1', '1', '1', '1', '1', '1', '1', '1', '1'},
                {'1', '0', '0', '1', '0', '0', '0', '1', '0', '1'},
                {'1', '0', '0', '1', '0', '0', '0', '1', '0', '1'},
                {'1', '0', '0', '0', '0', '1', '1', '0', '0', '1'},
                {'1', '0', '1', '1', '1', '0', '0', '0', '0', '1'},
                {'1', '0', '0', '0', '1', '0', '0', '0', '0', '1'},
                {'1', '0', '1', '0', '0', '0', '1', '0', '0', '1'},
                {'1', '0', '1', '1', '1', '0', '1', '1', '0', '1'},
                {'1', '1', '0', '0', '0', '0', '0', '0', '0', '1'},
                {'1', '1', '1', '1', '1', '1', '1', '1', '1', '1'}};
        /**/
        Maze maze = new Maze();
        maze.create(mazearr);
        System.out.println("");
        maze.print();


        /**/
        boolean flag = findPath(maze, 1, 1, 8, 8);
        if (flag) {
            System.out.println("");
            maze.print();
        } else {
            System.out.println("");
        }
    }
}

interface Cell {
    void setVisited(boolean b);
    void setMark(char m);
    char getMark();
    boolean isVisited();
    int getX();
    void setX(int x);
    int getY();
    void setY(int y);
}
